Tute (Week 4)

1 Defining the arithmetic of negative numbers

This question is related to the “How many elements does the Cartesian product of no sets have?” from an earlier quiz.

When people were figuring out how to reason with negative numbers, a question arose about multiplying two negative numbers: if −1×2 = −2, i.e. multiplication by −1 decreases +2 down to −2, shouldn’t multiplication of an (already) negative number by −1 “decrease it even more”?

(It was not the proverbial “ancient Greeks” who were worrying about this. It was European mathematicians in the 1700’s.)

Give an "explain like I'm five" style answer for why \(-2 \times -2 = 4\), similar to how a primary school teacher might explain \(2 \times 2 = 4\) by saying "if I take two apples twice, then I have four apples".
Give a rigorous argument for why, when \(z\) is negative, \(z \times -1\) shouldn't be negative. Hint: what algebraic laws would fail?

First, we might explain \(2 \times -2 = -4\) as "If I undo the act of taking two apples, twice, then I've lost four apples".

Then \(-2 \times -2 = 4\) could be stated as "If I undo the act of removing two apples, twice, then I have four apples".

(Granted, your average kindy student may still find all this a bit abstract.)
Suppose \(z \times -1 = -w\) for some positive \(w\). We will show that the cancellation law of multiplication fails: \[a * b = a * c \quad \equiv \quad b = c\] We have that \(w \times -1 = -w\), so \[z \times - 1 = w \times -1\] By the law of cancellation, we have \(z = w\), which leads to a contradiction since the LHS is negative and the RHS is positive.

Other similar derivations are possible for other laws. For example, we can show that the distributivity law \[a \times (b + c) = a\times b + a \times c\] fails. Consider the following derivation for a positize \(z\):
\begin{array}{ll} & 0 \\ = & -1 \times 0 \\ = & -1 \times (z + -z) \\ = & (-z) + (-1\times-z) \end{array}
If we require \(-1\times-z\) to be negative, we are forced to conclude that \(0\) is negative.

2 Reasoning carefully in everyday life

A speaker at a public seminar wants to make the point that most people know very little about elementary maths in the world around them.

“Look,” he says, “Here’s an example. Most people without a scientific background would not be able to tell me, to the nearest whole number, the length of the circumference of a circle that is 10 metres through the middle.”

(“Yeah, but what’s a circumference?!” shouts a voice from the back of the hall.)

“You sir,” he says to a man sitting in the front row. “What do you think?”
“I have absolutely no idea!”

“And you sir,” he says, pointing into the following row. “Not a bloody clue mate.”

“And you, madam?” he says, pointing right up the back.
“It’s just over 31 metres,” she replies. (Does her voice sound familiar?)
“Ah.” He pauses. “And what is your profession?”
“I’m a physicist.”

“See!?” he says. “A scientist! This lady proves my point.”

Does the woman’s answer really help to prove his point? If yes, why? If no, why not?

The speaker is making a claim about most people without a scientific background. The physicist has a scientific background, so the speaker makes no claim about her abilities. Thus, whether she can answer the question or not has no bearing on the speaker's point.

3 Tautologies

3.1 Question 1

Name at least two methods you could use to show that \(\varphi \rightarrow \psi\) is a tautology.

Here's a few:

Make a truth table for \((\varphi \rightarrow \psi)\), and check that all rows yield \(\top\).
Show that \(\varphi \models \psi\) by making truth tables for \(\varphi\) and \(\psi\), checking that they agree in all rows.
Give a proof for \(\vdash (\varphi \rightarrow \psi)\) – i.e. derive \((\varphi \rightarrow \psi)\) with no premises
Give a proof for \(\varphi \vdash \psi\)
Rewrite \(\varphi \rightarrow \psi\) into CNF, then check that every clause of the CNF formula has contradictory literals.

3.2 Question 2

Show that the following are tautologies:

\(P \rightarrow (Q \rightarrow P)\)
\((P \rightarrow (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow (P \rightarrow R))\)
\((\lnot P \rightarrow \lnot Q) \rightarrow (Q \rightarrow P)\)

With a truth table following approach (1):
\begin{array}{c|c|c|c} P & Q & Q \rightarrow P & P \rightarrow (Q \rightarrow P) \\ \hline \top & \top & \top & \color{red}{\top} \\ \top & \bot & \top & \color{red}\top \\ \bot & \top & \bot & \color{red}\top \\ \bot & \bot & \top & \color{red}\top \end{array}
The result follows because the red column is all \(\color{red}\top\).
Let's rewrite to CNF:
\begin{array}{ll} & (P \rightarrow (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow (P \rightarrow R)) \\ \equiv & (P \vee P \vee \neg P \vee R) \wedge (Q \vee P \vee \neg P \vee R) \wedge (\neg R \vee P \vee \neg P \vee R)\ \wedge \\ & (P \vee \neg Q \vee \neg P \vee R) \wedge (Q \vee \neg Q \vee \neg P \vee R) \wedge (\neg R \vee \neg Q \vee \neg P \vee R) \end{array}
Doing the full CNF conversion manually would be incredibly tedious (I used an automated tool). Nonetheless, once we have it it's easy to check that indeed, every clause has contradictory literals.
We use natural deduction: \[ \dfrac{ \dfrac{ \dfrac{ [Q] \quad \dfrac{[\neg P] \quad \lnot P \rightarrow \lnot Q} {\neg Q} \mathord\rightarrow\mbox{-E} } {\bot} \mathord\neg\mbox{-E} } {P} \mbox{IP} } {Q \rightarrow P} \mathord\rightarrow\mbox{-I} \]

4 Natural deduction

Using natural deduction, give a formal proof of the following:

\(Q \rightarrow (Q \land \lnot Q) \vdash \lnot Q\)
\((A \land B) \lor C \vdash B \lor C\)
\(\lnot A \rightarrow B, A \rightarrow C \vdash B \lor C\)
\(S \leftrightarrow T \vdash S \leftrightarrow (T \vee S)\)
\(C \rightarrow (E \land G) , \lnot C \rightarrow G \vdash G\)
\((W \lor X) \lor (Y \lor Z), X \rightarrow Y, \lnot Z \vdash W \lor Y\)

These are selected exercises from the forall x: Calgary textbook. Fitch-style proofs can be found in the textbook solutions for chapters 16 and and 19 in the 2020 version.

For diversity's sake we do a couple in other styles:

\[\dfrac { \dfrac{ [Q] \quad \dfrac{ \dfrac{[Q] \quad Q \rightarrow (Q \wedge \neg Q)} {Q \wedge \neg Q}\mathord{\rightarrow}\mbox{-E} } {\neg Q} \mathord{\wedge}\mbox{-I2} } { \bot } \mathord{\neg}\mbox{-E} } {\neg Q }\mbox{IP} \]
\[\begin{array}{ccccc} \mbox{Line} & \mbox{Premises} & \mbox{Formula} & \mbox{Rule} & \mbox{Ref} \\ \hline 1 & & (A \land B) \lor C & \mbox{Premise} & \\ 2 & & A \land B & \mbox{Premise} & \\ 3 & 2 & B & \mathord\land\mbox{-E} & 2 \\ 4 & 2 & B \lor C & \mathord\lor\mbox{-I} & 3 \\ 5 & & C & \mbox{Premise} & \\ 6 & 5 & B \lor C & \mathord\lor\mbox{-I} & 5 \\ 7 & 1 & B \lor C & \mathord\lor\mbox{-E} & 1,4,6 \end{array}\]